COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	{M2BDJ25.FNT[XGP,SYS]FAFDFA}
C00005 00003	{λ40JAFA}TITLE PAGE.{JR} AUGUST  1974.
C00007 00004	λ40FAJCFD} COPYRIGHT NOTICE.
C00008 00005	λ40FAJCFD} SIGNATURE  PAGE  FOR  Ph.D.  DISSERTATION.
C00010 00006	JCFD} LIST OF BOXES.
C00019 00007	JCFD} LIST OF FIGURES.
C00022 00008	JAJCFD} ACKNOWLEDGEMENTS.
C00024 ENDMK
C⊗;
{M2BDJ25.FNT[XGP,SYS];FA;FD;FA}
{H4;I∂0,1260;V∂0,0;}
{JA;FA}COVER PAGE.{JR} AUGUST  1974.
{JC} DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT -- DRAFT{
H4;JA;I∂10,0;V∂0,1260;}


{I400,0;JC;FD}          GEOMETRIC  MODELING  FOR  COMPUTER  VISION.

{I600,0;JC;FD}                   BRUCE  G.  BAUMGART

{I800,0;λ17;JUFA}ABSTRACT:

\The main  idea of  this thesis  is that  a three  dimensional
geometric  model of  the physical  world  is an  essential part  of a
general purpose  vision system.   Such a  model provides  a goal  for
descriptive  image   analysis,  an  origin  for   verification  image
synthesis,   and a context for spatial  problem solving.  Some of the
design ideas to  be presented have  been implemented in two  programs
named  GEOMED and CRE;  the programs  are demonstrated  in situations
involving camera motion relative to a static world.

{λ5;H4;I1600,0;V1600,1260;I1600,0;JU;F2}
	This research was supported in part  by the Advanced Research
Projects  Agency of  the  Office of  the Secretary  of  Defense under
Contract No. SD-183.
The views  and  conclusions contained  in this  document  are
those  of the  author and  should not  be interpreted  as necessarily
representing  the official policies, either  expressed or implied, of
the Advanced Research Project Agency or the United States Government.
{H4;I∂-20,0;V∂0,1260;JA}
{λ40;JA;FA}TITLE PAGE.{JR} AUGUST  1974.
{I400,0;JC;FD} GEOMETRIC  MODELING  FOR  COMPUTER  VISION.

{JCFA}                     A DISSERTATION
{JC}       SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE
{JC}            AND THE COMMITTEE ON GRADUATE STUDIES
{JC}                   OF STANFORD UNIVERSITY
{JC}         IN PARTIAL FULFILLMENT OF THE REQUIREMENTS
{JC}                      FOR THE DEGREE OF
{JC}                    DOCTOR OF PHILOSOPHY

{JC}                             BY
{JC}                  BRUCE  GUENTHER  BAUMGART
{JC}                         AUGUST  1974
{H4;I310,0;V310,1260;
I460,0;V460,1260;
I1020,0;V1020,1260;
I1260,0;V1260,1260;
I1900,0;JC;JUFA} - i -{Q;
λ40;FA;JCFD} COPYRIGHT NOTICE.

{I785,432;H4;C30;}

{I800,0;JC} C    COPYRIGHT 1974.

{I950,0;JC} BY

{I1100,0;JC} BRUCE  GUENTHER  BAUMGART

{I1900,0;JC;JUFA} - ii -{Q;
λ40;FA;JCFD} SIGNATURE  PAGE  FOR  Ph.D.  DISSERTATION.
{λ15;W300,1260-300;JU;FA}
\I certify that I have read this thesis and that in my
opinion it is fully adequate, in scope and quality, as a dissertation
for the degree of Doctor of Philosophy.{
H4;I∂80,630;V∂0,1260;}
{I∂0,630;}Principal Adviser

\I certify that I have read this thesis and that in my
opinion it is fully adequate, in scope and quality, as a dissertation
for the degree of Doctor of Philosophy.{
H4;I∂80,630;V∂0,1260;}


\I certify that I have read this thesis and that in my
opinion it is fully adequate, in scope and quality, as a dissertation
for the degree of Doctor of Philosophy.{
H4;I∂80,630;V∂0,1260;}


\I certify that I have read this thesis and that in my
opinion it is fully adequate, in scope and quality, as a dissertation
for the degree of Doctor of Philosophy.{
H4;I∂80,630;V∂0,1260;}


Approved for the University Committee on Graduate Studies:
{H4;I∂80,630;V∂0,1260;}
{W0,1260;I∂0,630;}Dean of Graduate Studies.
{JV;I1900,0;JC;JUFA} - iii -{Q;
JC;FD} LIST OF BOXES.
{JA;λ12;FA}
SECTION  0.	INTRODUCTION.

SECTION  1.	GEOMETRIC MODELING THEORY.
		1.1	Ten Kinds of Geometric Models.
		1.2	Desirable Properties for a Geometric Model.
		1.3	Properties of Polyhedra.

SECTION  2.	THE WINGED EDGE POLYHEDRON REPRESENTATION.
		2.1	Winged Edge Structures and Links.
		2.2	Lowest Level Winged Edge Routines.

SECTION  3.	A GEOMETRIC MODELING SYSTEM.
		3.1	The Euler Primitives.
		3.2	Routines Using the Euler Primitives.
		3.3	Euclidean Transformations.
		3.4	Tram Routines.
		3.5	Metric Routines.
		3.6	Space Routines.

SECTION  4.	HIDDEN LINE ELIMINATION FOR COMPUTER VISION.

SECTION  5.	A POLYHEDRON INTERSECTION ALGORITHM.

SECTION  6.	COMPUTER VISION THEORY.

SECTION  7.	VIDEO IMAGE CONTOURING.

SECTION  8.	IMAGE COMPARING.

SECTION  9.	CAMERA AND FEATURE LOCUS SOLVING.

SECTION 10.	RESULTS AND CONCLUSIONS.
{I1900,0;JC;JUFA} - vi -{Q;
JCFD} LIST OF FIGURES.
{JAFA}
SECTION  0.	INTRODUCTION.
	 0.1	Horse Shaped Polyhedra Derived from Video Images.
	 0.2	Model of Water Pump.
	 0.3	Example of Predicted Video and Perceived Video.
	 0.4	Example of Predicted and Perceived Contour Images.

SECTION  1.	GEOMETRIC MODELING THEORY.

SECTION  2.	THE WINGED EDGE POLYHEDRON REPRESENTATION.
	 2.1	Winged Edge Topology.
	 2.2	Three Kinds of Perimeters.
	 2.3	ESPLIT and KLEV.
	 2.4	MKFE and KLFE.
	 
SECTION  3.	A GEOMETRIC MODELING SYSTEM.
	 3.1	The 24 Dislays of Example #1.
	 3.2	The 24 Dislays of Example #2.
	 3.3	Five Kinds of Non-Solid Polyhedra.
	 3.4	Examples of MKCUBE, MKCYLN and MKBALL.
	 3.5	Creation of a Solid of Rotation by Sweeping a Wire.
	 3.6	Sweep and Glue.
	 3.7	Icosahedron by Prismoid sweep and pyramid sweep.
	 3.8	Three Cut Torus Dissection into Thirteen Parts.

SECTION  4.	HIDDEN LINE ELIMINATION FOR COMPUTER VISION.

SECTION  5.	A POLYHEDRON INTERSECTION ALGORITHM.
	 5.1	Polyhedron Intersection, Union and Subtraction.
	 5.2	Face Piercing Geometry.
	 5.3	Surface Edges and Interior Edges of Intersection.
	 5.4	Fetch Other Piercing Vertex of a Face.
	 5.5	Example of a Face Hole Fixup.
	 5.6	Examples of Face Convexity Coercion.
	 5.7	Body cutting illustrated.

SECTION  6.	COMPUTER VISION THEORY.

SECTION  7.	VIDEO IMAGE CONTOURING.

SECTION  8.	IMAGE COMPARING.

SECTION  9.	CAMERA AND FEATURE LOCUS SOLVING.

SECTION 10.	RESULTS AND CONCLUSIONS.
{I1900,0;JC;JUFA} - vii -{Q;
JAJCFD} ACKNOWLEDGEMENTS.
{FA}
The following people personally contributed to this work:

	Thesis Adviser:	{JC} John McCarthy
	Readers: {JC} Donald E. Knuth,  Alan C. Kay,  Ken Colby.

{JC} Jerry Agin, Leona Baumgart, Tom Binford, Jack Buchanan, Whitfield Diffie, Les Earnest,
{JC} Jerome Feldman, Tom Gafford, Steve Gibson, Ralph Gorin, Carl Hewett, Jack Holloway, Tovar Mock,
{JC} Andy Moorer, Hans Moravec, Richard Orban, Ted Panofsky, Lou Paul, Phip Petit, Dave Poole,
{JC} Lynn Quam, Jeff Raskin, Ron Rivest, Rod Schmidt, Irwin Sobel, Robert Sproull, Dan Swinehart,
{JC} Russel Taylor, Marty Tenenbaum, Larry Tesler, Arthur Thomas, Yorick Wilks, Fred Wright.



{JCFD} TYPOGRAPHY
{JU;FA}
	The orginal copy of this document was produced on a Xerox Graphics
Printer  with  a  resolution  of  two  hundred  point per  inch.  The
principal  font  is  News  Gothic  Boldface,  25  units  high,  which
originated  at  Carneige Mellon  University.  The  page layout,  text
justification, boxes, halftones and line drawings were done using the
author's  document formating  program,  XIP.  The source  files  were
prepared using the text editor,  E, created by Dan Swinehart and Fred
Wright.
	
{I1900,0;JC;JUFA} - viii -{